/**
 * Copyright 2012 Roman Seleznov
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License. 
 */

package com.romanapps.algorithms.sort;

import java.util.List;

public class InsertSort<T extends Comparable<? super T>> implements Sort<T>{

	@Override
	public List<T> sort(List<T> sortList) {
		
		for( int i = 1; i < sortList.size(); i++ ){	
			
			int insertPosition = -1;			
			final T currentItem = sortList.get( i );
			
			for( int j = i-1; j>-1; j--){
				
				final T previousItem = sortList.get( j );
				int result = previousItem.compareTo( currentItem );
				
				if( result > -1 ){					
					insertPosition = j;
					if( result == 0 ){
						break;
					}
				}else{
					break;
				}	
				
			}
			
			if( insertPosition > -1 ){				
				sortList.remove( i );
				sortList.add( insertPosition, currentItem );				
			}
			
		}
		
		return sortList;
	}
	
}